/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXB30/FONT#2=BAXI30[  P,JRA]/FONT#3=SUB/FONT#4=SET1/FONT#5=NGR20/FONT#6=GRK30/FONT#7=SUP/FONT#8=SPEC[  P,JRA]



␈↓ α∧␈↓␈↓ αdThe Post Correspondence Problem as a Question of Ambiguity

␈↓"∧␈↓ α∧␈↓␈↓ βα␈↓↓The Post Correspondence Problem as a Question of Ambiguity␈↓







␈↓"∀␈↓ α∧␈↓In␈α∂courses␈α∂dealing␈α∂with␈α∂computability␈α∂the␈α∂Post␈α∂Correspondence␈α∂Problem␈α∂(PCP)␈α∞is
␈↓ α∧␈↓usually␈α∩introduced␈α∩by␈α∩definition,␈α∩shown␈α∩to␈α⊃be␈α∩unsolvable␈α∩by␈α∩reducing␈α∩it␈α∩to␈α⊃the
␈↓ α∧␈↓halting␈α∂problem␈α∂(Minsky,␈α∂Manna),␈α∞and␈α∂disposed␈α∂of␈α∂as␈α∞yet␈α∂another␈α∂example␈α∂of␈α∞an
␈↓ α∧␈↓unsolvable␈α
class␈α
of␈α
questions.␈α
 Rarely␈αdo␈α
students␈α
get␈α
any␈α
real␈α
understanding␈αof␈α
what
␈↓ α∧␈↓the␈αPCP␈αis␈αand␈αwhere␈αdifficulties␈αlie␈αin␈αfinding␈αan␈αanswer␈αto␈αa␈αspecific␈αexample.␈α A
␈↓ α∧␈↓partial decision procedure can be very helpful in developing this understanding.

␈↓ α∧␈↓␈↓ αdThe␈α
Sardinas-Patterson␈α
test␈α
for␈α
ambiguity␈α
of␈α
a␈α
code␈α
provides␈α∞an␈α
algorithm
␈↓ α∧␈↓that␈α∂can␈α⊂be␈α∂modified␈α⊂to␈α∂search␈α⊂for␈α∂answers␈α∂to␈α⊂any␈α∂specific␈α⊂example␈α∂of␈α⊂the␈α∂PCP.
␈↓ α∧␈↓First,␈αwe␈αpresent␈α
the␈αSardinas-Patterson␈αtest.␈α
 Secondly,␈αwe␈αshow␈α
how␈αthe␈αtest␈αcan␈α
be
␈↓ α∧␈↓modified␈αto␈α
solve␈αa␈αproblem␈α
similar␈αbut␈αnot␈α
equivalent␈αto␈αthe␈α
PCP.␈α We␈α
then␈αstate
␈↓ α∧␈↓the␈αPost␈αCorrespondence␈αProblem␈αitself␈αand␈αdevelop␈αa␈αpartial␈αdecision␈αprocedure␈αby
␈↓ α∧␈↓a␈α∃further␈α∃modification␈α∃to␈α⊗the␈α∃algorithm.⊗↓It␈α∃is␈α∃suggested␈α∃that␈α⊗anyone␈α∃already
␈↓ α∧␈↓familiar with the Sardinas-Patterson test skip to section 2.←



␈↓ α∧␈↓␈↓ αdA␈α
␈↓αcode␈↓␈αis␈α
a␈α
set␈αof␈α
code␈α
words,␈αor␈α
strings,␈α
from␈αsome␈α
given␈α
finite␈αalphabet,␈α
e.g.,
␈↓ α∧␈↓for␈α
the␈α
alphabet␈α{0,␈α
1},␈α
a␈αsample␈α
code␈α
is␈α
{001,␈α01,␈α
0100,␈α
101}.␈α A␈α
code␈α
is␈αambiguous␈α
if
␈↓ α∧␈↓there␈αexists␈αa␈αstring␈αwhich␈αcan␈αbe␈αinterpreted,␈αor␈αparsed,␈αin␈αtwo␈αdifferent␈α
ways.␈αFor
␈↓ α∧␈↓example,␈α∂with␈α∂the␈α∂given␈α∂code,␈α∂the␈α∂string␈α∂"0100101"␈α∂ can␈α∂be␈α∂parsed␈α∂as␈α∂a␈α⊂string␈α∂of
␈↓ α∧␈↓three␈α∂words,␈α∂"01.001.01",␈α∂or␈α∂as␈α∂a␈α∞string␈α∂of␈α∂two␈α∂words,␈α∂"0100.101".␈α∂  The␈α∞Sardinas-
␈↓ α∧␈↓Patterson␈αtest␈αprovides␈αan␈αalgorithm␈αfor␈αdetermining␈αwhether␈αor␈αnot␈αa␈αgiven␈αcode␈αis
␈↓ α∧␈↓ambiguous,␈αand,␈αif␈αit␈αis,␈αthe␈αtest␈αalso␈αprovides␈αthe␈αmeans␈αof␈αconstructing␈αan␈αexample
␈↓ α∧␈↓ambiguous string.

␈↓ α∧␈↓␈↓ αdIf␈α␈↓εa␈↓=␈↓εbg␈↓,␈αwhere␈α␈↓εa␈↓,␈α␈↓εb␈↓,␈αand␈α␈↓εg␈↓␈αare␈α
strings,␈αthen␈α␈↓εb␈↓␈αis␈αsaid␈αto␈αbe␈αa␈α"prefix"␈α
of␈α␈↓εa␈↓
␈↓ α∧␈↓and␈α∞␈↓εg␈↓␈α∞is␈α∞called␈α∞the␈α
"tail".␈α∞ If␈α∞there␈α∞exists␈α∞an␈α
ambiguous␈α∞string,␈α∞then␈α∞it␈α∞must␈α
begin
␈↓ α∧␈↓with␈α∞a␈α∂code␈α∞word␈α∂which␈α∞is␈α∂ the␈α∞prefix␈α∂of␈α∞another␈α∂code␈α∞word.␈α∂The␈α∞tail␈α∂must␈α∞then
␈↓ α∧␈↓form␈α
a␈α
prefix␈α
of␈α
some␈α∞code␈α
word.␈α
 With␈α
each␈α
tail␈α∞we␈α
keep␈α
track␈α
of,␈α
we␈α∞are␈α
saying
␈↓ α∧␈↓that␈α
there␈α
is␈α
a␈α
string␈α
that␈α
is␈α
ambiguous␈α
up␈α
to␈α
a␈α
point,␈α
but␈α
we␈α
have␈α
this␈α
overhang,
␈↓ α∧␈↓this tail, which must still be incorporated as a legal code sequence.

␈↓ α∧␈↓␈↓ αd␈↓↓Sardinas-Patterson␈α≠Test␈↓⊗↓The␈α≠algorithm␈α≠given␈α≠was␈α≠presented␈α≠by␈α≠D.
␈↓ α∧␈↓Huffman␈αin␈αan␈αInformation␈αSciences␈αcourse␈αat␈αthe␈αUniversity␈αof␈αCalifornia␈αat␈αSanta
␈↓ α∧␈↓Cruz.←:
␈↓ α∧␈↓We make a table, entering the code words in column 0.  We add entries in the rest o



␈↓ α∧␈↓␈↓ αdthe columns according to the following rules:
␈↓ α∧␈↓␈↓ αd     
␈↓ α∧␈↓␈↓ αd        1)  to construct column 1, check column 0 to see if any of the code wor
␈↓ α∧␈↓␈↓ αd        is a prefix of any other code word.
␈↓ α∧␈↓␈↓ αd                a)  if there is no such pair of code words, then the code is not
␈↓ α∧␈↓␈↓ αd                ambiguous.
␈↓ α∧␈↓␈↓ αd                b)  for each such pair that can be found, enter the "tail" in
␈↓ α∧␈↓␈↓ αd                column 1, and proceed.
␈↓ α∧␈↓␈↓ αd    
␈↓ α∧␈↓␈↓ αd        2)  to construct column n+1 (n≥1):
␈↓ α∧␈↓␈↓ αd                a)  examine column n for any word13hich is a prefix of some wo
␈↓ α∧␈↓␈↓ αd                in column 0.  For each such pair, enter the tail in column n+1.
␈↓ α∧␈↓␈↓ αd                b) Examine column 0 for any word13hich is a prefix of some wo
␈↓ α∧␈↓␈↓ αd                in column n.  For each such pair, enter the tail in column n+1.
␈↓ α∧␈↓␈↓ αd     
␈↓ α∧␈↓␈↓ αd        3)  Continue the process of creating new columns by computing tails u
␈↓ α∧␈↓␈↓ αd                a)  No entries are found for a new column - in this case the code
␈↓ α∧␈↓␈↓ αd                is not ambiguous.
␈↓ α∧␈↓␈↓ αd                b)  A tail created in some column is one of the original code
␈↓ α∧␈↓␈↓ αd                words. In this case the code is ambiguous and an example can be
␈↓ α∧␈↓␈↓ αd                constructed from the entries in the table.
␈↓ α∧␈↓␈↓ αd                c)  A column is repeated - at this point we know we shall be
␈↓ α∧␈↓␈↓ αd                forever repeating the same pattern, as the construction of new
␈↓ α∧␈↓␈↓ αd                columns depends only on the single previous column and the
␈↓ α∧␈↓␈↓ αd                original code in column 0.  In this case the code is again
␈↓ α∧␈↓␈↓ αd                unambiguous.
␈↓ α∧␈↓␈↓ αd     

␈↓ α∧␈↓For␈α
example,␈α∞for␈α
the␈α
code␈α∞given␈α
above,␈α
the␈α∞algorithm␈α
yields␈α
the␈α∞table␈α
of␈α∞Figure␈α
1.
␈↓ α∧␈↓The␈α∂ambiguous␈α∂string␈α∂"0100101"␈α∂can␈α∂be␈α∞constructed␈α∂by␈α∂tracing␈α∂the␈α∂history␈α∂of␈α∞the
␈↓ α∧␈↓marked entry. It yields the two parses "01.001.01." and "0100.101.".
␈↓ α∧␈↓␈↓ αd                  0      1       2       3
␈↓ α∧␈↓␈↓ αd                ______________________________
␈↓ α∧␈↓␈↓ αd                001     00       1      01 *** this tail is also a code word!***
␈↓ α∧␈↓␈↓ αd                 01
␈↓ α∧␈↓␈↓ αd               0100
␈↓ α∧␈↓␈↓ αd                101
␈↓ α∧␈↓␈↓ αd                                 Figure 1.

␈↓ α∧␈↓ The␈α∂number␈α∂of␈α∂columns␈α∂created␈α∂in␈α∂this␈α∂process␈α∂gives␈α∂an␈α∂indication␈α∂of␈α⊂the␈α∂delay
␈↓ α∧␈↓required,␈α∂in␈α∂the␈α∂worst␈α∂case,␈α∂to␈α∂resolve␈α∂any␈α∂temporary␈α∂ambiguity␈α∂which␈α∂may␈α∞occur
␈↓ α∧␈↓even␈αwhen␈αthe␈α
code␈αitself␈αis␈α
unambiguous.␈α If␈αthe␈α
algorithm␈αstops␈αin␈α
condition␈α3)c),
␈↓ α∧␈↓then␈α
there␈α
is␈α
no␈α
bound␈α
on␈α
this␈α
delay;␈αwe␈α
may␈α
have␈α
to␈α
wait␈α
until␈α
the␈α
entire␈αmessage␈α
is
␈↓ α∧␈↓received before we can start decoding it.



␈↓ α∧␈↓␈↓ αdSuppose␈α∀we␈α∀are␈α∀given␈α∪a␈α∀finite␈α∀set␈α∀of␈α∪ordered␈α∀pairs␈α∀of␈α∀strings␈α∪{(␈↓εa␈↓β1␈↓,␈↓εb␈↓β1␈↓),
␈↓ α∧␈↓...,(␈↓εa␈↓βn␈↓,␈↓εb␈↓βn␈↓)}␈α
and␈αasked␈α
to␈α
determine␈αwhether␈α
or␈α
not␈αindices␈α
i␈↓β1␈↓,␈α...,␈α
i␈↓βk␈↓␈α
and␈αj␈↓β1␈↓,␈α
...,␈α
j␈↓βr␈↓␈αexist
␈↓ α∧␈↓such␈αthat␈α␈↓εa␈↓βi␈↓#v1␈↓#␈↓...␈↓εa␈↓βi␈↓#vk␈↓#␈↓␈α=␈α␈↓εb␈↓βj␈↓#v1␈↓#␈↓...␈↓εb␈↓βj␈↓#vr␈↓#␈↓.␈α That␈αis,␈αwe␈αmust␈αbe␈αable␈αto␈αdecide␈αwhether␈αthere␈αexists
␈↓ α∧␈↓a␈αstring␈αthat␈αcan␈αbe␈αinterpreted␈αas␈αconsisting␈αeither␈αentirely␈αof␈α␈↓εa␈↓'s␈αor␈αentirely␈αof␈α␈↓εb␈↓'s,
␈↓ α∧␈↓and produce the string if it does exist.

␈↓ α∧␈↓␈↓ αd        This␈α
time␈α
we␈α
make␈αa␈α
table␈α
with␈α
pairs␈α
of␈αcolumns␈α
since␈α
we␈α
need␈αto␈α
keep
␈↓ α∧␈↓the␈α␈↓εa␈↓'s␈αseparated␈αfrom␈αthe␈α␈↓εb␈↓'s.␈α To␈αget␈αstarted␈αwe␈αmust␈αfind␈αan␈α␈↓εa␈↓βi␈↓␈αand␈α␈↓εb␈↓βj␈↓␈α
such␈αthat
␈↓ α∧␈↓one␈αis␈αthe␈αprefix␈αof␈αthe␈αother.␈α The␈αtail␈αmust␈αthen␈αbe␈αinterpretable␈αas␈αthe␈αbeginning
␈↓ α∧␈↓of␈αeither␈α
a␈αstring␈αof␈α
␈↓εa␈↓'s␈α(if␈α
␈↓εa␈↓βi␈↓␈αwas␈αthe␈α
prefix␈αof␈α␈↓εb␈↓βj␈↓)␈α
or␈αa␈α
string␈αof␈α␈↓εb␈↓'s␈α
(if␈α␈↓εb␈↓βj␈↓␈α
was␈αthe
␈↓ α∧␈↓prefix of ␈↓εa␈↓βi␈↓).

␈↓ α∧␈↓␈↓ αdSuppose␈αthat␈αwe␈αhave␈αalready␈αlisted␈αn␈αcolumns␈αin␈αthe␈αtable.␈αEach␈αentry␈α␈↓εg␈↓␈αin
␈↓ α∧␈↓column␈αn␈↓βα␈↓␈αindicates␈αthat␈αa␈αstring␈α␈↓εs␈↓␈αcan␈αbe␈αconstructed␈αwhich␈αmay␈αbe␈αinterpreted␈αas
␈↓ α∧␈↓consisting␈αentirely␈αof␈α␈↓εb␈↓'s,␈αor␈αentirely␈αof␈α␈↓εa␈↓'s␈αwith␈αthe␈αstring␈α␈↓εg␈↓␈αon␈αthe␈αend.␈αThat␈αis,␈α
the
␈↓ α∧␈↓string␈α
␈↓εs␈↓ = a␈↓β1␈↓...a␈↓βk␈↓a␈↓βk+1␈↓...a␈↓βn␈↓␈α(where␈α
each␈αa␈↓βi␈↓␈α
is␈αa␈α
letter␈αof␈α
the␈αcode␈α
alphabet)␈αis␈α
the␈αsame␈α
as
␈↓ α∧␈↓␈↓εb␈↓βj␈↓#v1␈↓#␈↓...␈↓εb␈↓βj␈↓#vm␈↓#␈↓ for some ␈↓βj␈↓#v1␈↓#␈↓...␈↓βj␈↓#vm␈↓#␈↓, and the same as ␈↓εa␈↓βi␈↓#v1␈↓#␈↓...␈↓εa␈↓βi␈↓#vp␈↓#␈↓εg␈↓ for some ␈↓βi␈↓#v1␈↓#␈↓...␈↓βi␈↓#vp␈↓#␈↓.

␈↓ α∧␈↓␈↓ αd If␈α
␈↓εg␈↓␈α
itself␈α
is␈α
an␈α␈↓εa␈↓,␈α
then␈α
we␈α
are␈α
done;␈α
but␈αif␈α
not,␈α
we␈α
must␈α
continue␈αour␈α
search.
␈↓ α∧␈↓If␈α␈↓εg␈↓␈αis␈α
a␈αprefix␈αof␈α
an␈α␈↓εa␈↓βi␈↓,␈αthen␈αwe␈α
extend␈αour␈αstring␈α
of␈α␈↓εa␈↓'s␈αby␈α
that␈α␈↓εa␈↓βi␈↓,␈αresulting␈αin␈α
the
␈↓ α∧␈↓string␈αwe␈αhad␈αbefore␈αwith␈αthe␈αaddition␈αof␈αthe␈αnew␈αtail␈αon␈αthe␈αend.␈α This␈αstring␈αcan
␈↓ α∧␈↓be␈α∩interpreted␈α⊃as␈α∩consisting␈α∩entirely␈α⊃of␈α∩␈↓εa␈↓'s,␈α∩or␈α⊃entirely␈α∩of␈α∩␈↓εb␈↓'s␈α⊃with␈α∩the␈α∩new␈α⊃tail
␈↓ α∧␈↓appended to the end. Thus, we must add the new tail to the column (n+1)␈↓ββ␈↓.

␈↓ α∧␈↓␈↓ αdIf␈αsome␈α
␈↓εa␈↓βi␈↓␈αis␈α
a␈αprefix␈α
of␈α␈↓εg␈↓,␈α
then␈αwe␈α
have␈αextended␈α
our␈α␈↓εa␈↓-interpretation␈αof␈α
␈↓εs␈↓,
␈↓ α∧␈↓and␈α
the␈α
new␈α
tail␈α
is␈α
the␈α
"leftover"␈α
in␈α
the␈α
same␈α
sense␈α
that␈α
␈↓εg␈↓␈α
was.␈α
 Thus␈α
we␈α∞add␈α
the
␈↓ α∧␈↓new tail to column (n+1)␈↓βα␈↓.

␈↓ α∧␈↓␈↓ αdWe␈α∞do␈α∞an␈α∞analogous␈α∞examination␈α∞of␈α∞column␈α∞n␈↓ββ␈↓.␈α∞ If␈α∞we␈α∞ever␈α∞find␈α∞an␈α∂␈↓εa␈↓βi␈↓␈α∞in
␈↓ α∧␈↓some␈α⊂column␈α⊂n␈↓βα␈↓,␈α⊂or␈α⊂a␈α⊂␈↓εb␈↓βj␈↓␈α⊂in␈α⊂some␈α⊂column␈α⊂n␈↓ββ␈↓,␈α⊂then␈α⊂we␈α⊂are␈α⊂through.␈α⊂ There␈α⊂is␈α∂a
␈↓ α∧␈↓solution␈αstring␈αand␈αit␈αcan␈αbe␈αconstructed␈αby␈αtracing␈αthe␈αhistory␈αof␈αthe␈αentry␈α␈↓εa␈↓βi␈↓␈αin␈α
n␈↓βα␈↓,
␈↓ α∧␈↓or ␈↓εb␈↓βj␈↓ in n␈↓ββ␈↓, as the case may be.

␈↓ α∧␈↓␈↓ αdThis discussion is summarized as the following algorithm:
␈↓ α∧␈↓␈↓ αd    
␈↓ α∧␈↓␈↓ αd        1)  Enter the ␈↓εa␈↓'s and ␈↓εb␈↓'s in columns 0␈↓βα␈↓ and 0␈↓ββ␈↓, respectively.
␈↓ α∧␈↓␈↓ αd     
␈↓ α∧␈↓␈↓ αd        2)  Create columns 1␈↓βα␈↓ and 1␈↓ββ␈↓ :
␈↓ α∧␈↓␈↓ αd                a)  If any ␈↓εa␈↓βi␈↓ is a prefix of any ␈↓εb␈↓βj␈↓, enter the tail in 1␈↓βα␈↓.
␈↓ α∧␈↓␈↓ αd                b)  If any ␈↓εb␈↓βi␈↓ is a prefix of any ␈↓εa␈↓βj␈↓, enter the tail in 1␈↓ββ␈↓.
␈↓ α∧␈↓␈↓ αd    
␈↓ α∧␈↓␈↓ αd        3)  To create columns (n+1)␈↓βα␈↓ and (n+1)␈↓ββ␈↓ :
␈↓ α∧␈↓␈↓ αd                a1)  If any string in n␈↓βα␈↓ is a prefix of any ␈↓εa␈↓βi␈↓,
␈↓ α∧␈↓␈↓ αd                enter the tail in (n+1)␈↓ββ␈↓.
␈↓ α∧␈↓␈↓ αd                a2)  If any ␈↓εa␈↓βi␈↓ is a prefix of any string in n␈↓βα␈↓,
␈↓ α∧␈↓␈↓ αd                enter the tail in (n+1)␈↓βα␈↓.



␈↓ α∧␈↓␈↓ αd                b1)  If any string in n␈↓ββ␈↓ is a prefix of any ␈↓εb␈↓βi␈↓,
␈↓ α∧␈↓␈↓ αd                enter the tail in (n+1)␈↓βα␈↓.
␈↓ α∧␈↓␈↓ αd                b2)  If any ␈↓εb␈↓βi␈↓ is a prefix of any string in n␈↓ββ␈↓,
␈↓ α∧␈↓␈↓ αd                enter the tail in (n+1)␈↓ββ␈↓.
␈↓ α∧␈↓␈↓ αd    
␈↓ α∧␈↓␈↓ αd        4)  Continue creating new columns according to step 3) until one of the
␈↓ α∧␈↓␈↓ αd          following conditions occurs:
␈↓ α∧␈↓␈↓ αd                a)  The process closes out, that is, the entries in n␈↓βα␈↓ and n␈↓ββ␈↓
␈↓ α∧␈↓␈↓ αd                  are such that the columns (n+1)␈↓βα␈↓ and (n+1)␈↓ββ␈↓ are empty.  In
␈↓ α∧␈↓␈↓ αd                  this case we can say that no solution is possible.
␈↓ α∧␈↓␈↓ αd                b)  Some column n␈↓βα␈↓ contains an ␈↓εa␈↓βi␈↓, or some column n␈↓ββ␈↓ contains
␈↓ α∧␈↓␈↓ αd                  a ␈↓εb␈↓βi␈↓; then a solution exists and can be found by tracing the
␈↓ α∧␈↓␈↓ αd                  history of such an entry through the table.
␈↓ α∧␈↓␈↓ αd                c)  A pattern of columns develops which will continue infinitely,
␈↓ α∧␈↓␈↓ αd                  that is, an ␈↓εa␈↓-␈↓εb␈↓ pair of columns is repeated; then there is no
␈↓ α∧␈↓␈↓ αd                  solution. New columns depend only on the single previous pair 
␈↓ α∧␈↓␈↓ αd                  columns and the original columns 0␈↓βα␈↓ and 0␈↓ββ␈↓. Therefore
␈↓ α∧␈↓␈↓ αd                  once any n␈↓βα␈↓-n␈↓ββ␈↓ pair of columns is repeated, the same
␈↓ α∧␈↓␈↓ αd                  columns will follow the pair ad infinitum.

␈↓ α∧␈↓␈↓ αd     One␈α∂of␈α⊂the␈α∂conditions␈α⊂4)a)␈α∂-␈α∂4)c)␈α⊂is␈α∂guaranteed␈α⊂to␈α∂occur.␈α⊂ Since␈α∂"tails"
␈↓ α∧␈↓have␈αlength␈αless␈αthan␈αsome␈αcode,␈αand␈αthere␈αis␈αa␈αmaximum␈αlength␈αamong␈αthe␈α␈↓εa␈↓βi␈↓␈αand
␈↓ α∧␈↓␈↓εb␈↓βi␈↓,␈α∩there␈α⊃is␈α∩a␈α⊃maximum␈α∩tail␈α∩length,␈α⊃and␈α∩thus␈α⊃a␈α∩finite␈α⊃number␈α∩of␈α∩possible␈α⊃tails.
␈↓ α∧␈↓Therefore, only a finite number of n␈↓βα␈↓-n␈↓ββ␈↓ column pairs is possible.

␈↓ α∧␈↓␈↓ αd    The␈α≠difference␈α≠between␈α≠the␈α≠problem␈α≠stated␈α≠above␈α≠and␈α≠the␈α~Post
␈↓ α∧␈↓Correspondence␈α
Problem␈α
is␈α
that␈α
we␈α
were␈α
not␈α
restricted␈α
to␈α
using␈α
the␈α∞same␈α
indexing
␈↓ α∧␈↓sequence␈α∞for␈α∞both␈α∞␈↓εa␈↓'s␈α∞and␈α∞␈↓εb␈↓'s.␈α∞The␈α∞following␈α∞statement␈α∞of␈α∞the␈α∞PCP␈α∞is␈α∞taken␈α
from
␈↓ α∧␈↓Minsky.

␈↓ α∧␈↓␈↓ β$␈↓↓Post Correspondence Problem:␈↓

␈↓ α∧␈↓␈↓ β$Given␈αan␈αalphabet␈αA␈αand␈αa␈αfinite␈αset␈αof␈αpairs␈αof␈αwords␈α(␈↓εa␈↓βi␈↓,
␈↓ α∧␈↓␈↓ β$␈↓εb␈↓βi␈↓)␈α⊂in␈α⊂the␈α⊂alphabet␈α∂A,␈α⊂is␈α⊂there␈α⊂a␈α∂sequence␈α⊂i␈↓β1␈↓,␈α⊂i␈↓β2␈↓,␈α⊂...,␈α⊂i␈↓βn␈↓␈α∂of
␈↓ α∧␈↓␈↓ β$selections such that the strings
␈↓ α∧␈↓␈↓ ¬␈↓εa␈↓βi␈↓#v1␈↓#␈↓εa␈↓βi␈↓#v2␈↓#␈↓...␈↓εa␈↓βi␈↓#vn␈↓#␈↓ and ␈↓εb␈↓βi␈↓#v1␈↓#␈↓εb␈↓βi␈↓#v2␈↓#␈↓...␈↓εb␈↓βi␈↓#vn␈↓#␈↓

␈↓ α∧␈↓␈↓ β$formed␈α#by␈α"concatenating--writing␈α#down␈α#in␈α"order--
␈↓ α∧␈↓␈↓ β$corresponding ␈↓εa␈↓'s and ␈↓εb␈↓'s are identical?

␈↓ α∧␈↓␈↓ αdWe␈αcan␈αmodify␈αthe␈αtable␈αbuilding␈αprocedure␈αfurther␈αto␈αsearch␈αfor␈αa␈αsolution
␈↓ α∧␈↓to␈α
the␈αPCP,␈α
providing␈αa␈α
partial␈αdecision␈α
procedure.␈α
 If␈αa␈α
solution␈αexists,␈α
then␈αwe␈α
will
␈↓ α∧␈↓find␈α∞it,␈α∞but␈α∞if␈α∂there␈α∞is␈α∞no␈α∞solution␈α∂we␈α∞may␈α∞end␈α∞up␈α∂looking␈α∞forever␈α∞as␈α∞we␈α∂lose␈α∞the
␈↓ α∧␈↓guarantee␈α⊃of␈α⊂termination␈α⊃provided␈α⊃by␈α⊂the␈α⊃algorithm␈α⊃above.␈α⊂ As␈α⊃an␈α⊃example,␈α⊂we
␈↓ α∧␈↓construct a solution for the set of pairs {(1,111), (10111,10), (10,0)} in Figure 2.



␈↓ α∧␈↓␈↓ αdWe␈αagain␈αbuild␈αa␈αtable␈αwith␈αcolumn␈αpairs.␈α This␈αtime,␈αto␈αget␈αstarted␈αwe␈αmust
␈↓ α∧␈↓find␈αan␈α␈↓εa␈↓βi␈↓␈α
and␈α␈↓εb␈↓βi␈↓␈α(with␈αthe␈α
␈↓αsame␈↓␈αindex)␈αsuch␈α
that␈αone␈αis␈αa␈α
prefix␈αof␈αthe␈α
other.␈α As
␈↓ α∧␈↓we␈αcontinue␈αlisting␈αcolumns,␈αwe␈αmust␈αbe␈αcareful␈αto␈αensure␈αthat␈αwe␈αare␈αconstructing␈αa
␈↓ α∧␈↓string␈αinterpretable␈αas␈αa␈αsequence␈αof␈α␈↓εa␈↓βi␈↓'s␈αand␈αalso␈αas␈αthe␈α␈↓αsame␈αsequence␈↓␈αof␈α␈↓εb␈↓βi␈↓'s.␈αEvery
␈↓ α∧␈↓time we make use of an ␈↓εa␈↓βi␈↓ we must also be able to use the corresponding ␈↓εb␈↓βi␈↓.
␈↓ α∧␈↓␈↓ αd        1)  Enter the ␈↓εa␈↓'s and ␈↓εb␈↓'s in columns 0␈↓βα␈↓ and 0␈↓ββ␈↓, respectively, being
␈↓ α∧␈↓␈↓ αd          careful to enter them in order.
␈↓ α∧␈↓␈↓ αd    
␈↓ α∧␈↓␈↓ αd        2)  Create columns 1␈↓βα␈↓ and 1␈↓ββ␈↓:
␈↓ α∧␈↓␈↓ αd                a)  If any ␈↓εa␈↓βi␈↓ is a prefix of ␈↓εb␈↓βi␈↓ (note the same index is required),
␈↓ α∧␈↓␈↓ αd                  then enter the tail in 1␈↓βα␈↓.
␈↓ α∧␈↓␈↓ αd                b)  If any ␈↓εb␈↓βi␈↓ is a prefix of the corresponding ␈↓εa␈↓βi␈↓, then enter the
␈↓ α∧␈↓␈↓ αd                  tail in 1␈↓ββ␈↓.
␈↓ α∧␈↓␈↓ αd     
␈↓ α∧␈↓␈↓ αd        3)  Create columns (n+1)␈↓βα␈↓ and (n+1)␈↓ββ␈↓:
␈↓ α∧␈↓␈↓ αd                a1)  If any string in n␈↓βα␈↓ is an ␈↓εa␈↓βi␈↓, write the corresponding ␈↓εb␈↓βi␈↓ in
␈↓ α∧␈↓␈↓ αd                   column (n+1)␈↓βα␈↓.
␈↓ α∧␈↓␈↓ αd                a2)  If any string in n␈↓βα␈↓ is a prefix of any ␈↓εa␈↓βi␈↓, check the tail:
␈↓ α∧␈↓␈↓ αd                          i)  If the tail is the corresponding ␈↓εb␈↓βi␈↓, then we have
␈↓ α∧␈↓␈↓ αd                            a solution!
␈↓ α∧␈↓␈↓ αd                         ii)  If the tail is a prefix of the corresponding ␈↓εb␈↓βi␈↓,
␈↓ α∧␈↓␈↓ αd                            enter the ␈↓αnew␈↓ tail (i.e., what is left of ␈↓εb␈↓βi␈↓ after
␈↓ α∧␈↓␈↓ αd                            deleting the tail from the front of it) in (n+1)␈↓βα␈↓.
␈↓ α∧␈↓␈↓ αd                        iii)  If the corresponding ␈↓εb␈↓βi␈↓ is a prefix of the tail,
␈↓ α∧␈↓␈↓ αd                            enter the new tail in (n+1)␈↓ββ␈↓.
␈↓ α∧␈↓␈↓ αd                a3)  If any ␈↓εa␈↓βi␈↓ is a prefix of any string in n␈↓βα␈↓, add the corre-
␈↓ α∧␈↓␈↓ αd                   sponding ␈↓εb␈↓βi␈↓ to the end of the tail, and enter the whole thing
␈↓ α∧␈↓␈↓ αd                   in column (n+1)␈↓βα␈↓. (e.g. In Figure 2, the entry "1111" in column
␈↓ α∧␈↓␈↓ αd                   2␈↓βα␈↓, results from "1", in 0␈↓βα␈↓, being a prefix of "11", in 1␈↓βα␈↓,
␈↓ α∧␈↓␈↓ αd                   thus "111", ␈↓εb␈↓β1␈↓, was added to the tail "1". Again, in 3␈↓βα␈↓,
␈↓ α∧␈↓␈↓ αd                   "1", in 0␈↓βα␈↓, is a prefix of "1111", in 2␈↓βα␈↓, so "111", ␈↓εb␈↓β1␈↓,
␈↓ α∧␈↓␈↓ αd                   is added to the tail, producing the entry "111111".)
␈↓ α∧␈↓␈↓ αd    
␈↓ α∧␈↓␈↓ αd                b1)  If any string in n␈↓ββ␈↓ is an ␈↓εb␈↓βi␈↓, write the corresponding ␈↓εa␈↓βi␈↓ in
␈↓ α∧␈↓␈↓ αd                   column (n+1)␈↓ββ␈↓. (e.g. In column 1␈↓ββ␈↓, "111" appears, thus "1",
␈↓ α∧␈↓␈↓ αd                   the corresponding ␈↓εa␈↓βi␈↓, appears in 2␈↓ββ␈↓.)
␈↓ α∧␈↓␈↓ αd                b2)  If any string in n␈↓ββ␈↓ is a prefix of any ␈↓εb␈↓βi␈↓, check the tail:
␈↓ α∧␈↓␈↓ αd                          i)  If the tail is the corresponding ␈↓εa␈↓βi␈↓, then we have
␈↓ α∧␈↓␈↓ αd                            a solution!
␈↓ α∧␈↓␈↓ αd                         ii)  If the tail is a prefix of the corresponding ␈↓εa␈↓βi␈↓,
␈↓ α∧␈↓␈↓ αd                            enter the ␈↓αnew␈↓ tail in (n+1)␈↓ββ␈↓.
␈↓ α∧␈↓␈↓ αd                        iii)  If the corresponding ␈↓εa␈↓βi␈↓ is a prefix of the tail,
␈↓ α∧␈↓␈↓ αd                            enter the new tail in (n+1)␈↓βα␈↓. (e.g. In Figure 2,
␈↓ α∧␈↓␈↓ αd                            column 2␈↓ββ␈↓ contains "1", which is a prefix of ␈↓εb␈↓β1␈↓;
␈↓ α∧␈↓␈↓ αd                            the tail is "11"; the corresponding ␈↓εa␈↓β1␈↓ is "1",
␈↓ α∧␈↓␈↓ αd                            which is a prefix of the tail "11", thus the ␈↓αnew␈↓
␈↓ α∧␈↓␈↓ αd                            tail is "1" and is entered in 3␈↓βα␈↓.)
␈↓ α∧␈↓␈↓ αd                b3)  If any ␈↓εb␈↓βi␈↓ is a prefix of any string in n␈↓ββ␈↓, add the corre-



␈↓ α∧␈↓␈↓ αd                   sponding ␈↓εa␈↓βi␈↓ to the end of the tail, and enter the whole thing
␈↓ α∧␈↓␈↓ αd                   in column (n+1)␈↓ββ␈↓.
␈↓ α∧␈↓␈↓ αd    

␈↓ α∧␈↓ To␈α∞facilitate␈α∞the␈α∞construction␈α∞of␈α∞our␈α
solution␈α∞we␈α∞subscript␈α∞each␈α∞entry␈α∞in␈α∞the␈α
table
␈↓ α∧␈↓with␈α∂the␈α∂index␈α∂of␈α∂the␈α⊂pair␈α∂used␈α∂in␈α∂deriving␈α∂it.␈α⊂ We␈α∂also␈α∂use␈α∂arrows␈α∂to␈α⊂trace␈α∂the
␈↓ α∧␈↓history␈α⊂of␈α∂entries.␈α⊂Then,␈α⊂when␈α∂we've␈α⊂found␈α∂that␈α⊂a␈α⊂solution␈α∂exists,␈α⊂we␈α⊂can␈α∂simply
␈↓ α∧␈↓follow␈α
the␈α
path␈α
from␈α
the␈α
first␈α
column␈α
pair,␈α
noting␈α
the␈α
subscripts␈α
as␈α
we␈α
go,␈α
and␈αwe
␈↓ α∧␈↓are␈αleft␈α
with␈αthe␈α
desired␈αlist␈α
of␈αindices.␈α
If␈αa␈α
solution␈αexists,␈α
it␈αmust␈α
be␈αconstructable
␈↓ α∧␈↓by the given rules.
␈↓ α∧␈↓␈↓ αd    
␈↓ α∧␈↓␈↓ αd        0␈↓βα␈↓    0␈↓ββ␈↓        1␈↓βα␈↓    1␈↓ββ␈↓       2␈↓βα␈↓      2␈↓ββ␈↓      3␈↓βα␈↓      3␈↓ββ␈↓      4␈↓βα␈↓    4␈↓ββ␈↓
␈↓ α∧␈↓␈↓ αd     ___________________________________________________________________
␈↓ α∧␈↓␈↓ αd    
␈↓ α∧␈↓␈↓ αd         1     111      11␈↓β(1)␈↓          1111␈↓β(1)␈↓      111111␈↓β(1)␈↓
␈↓ α∧␈↓␈↓ αd     10111     10             111␈↓β(2)␈↓          1␈↓β(1)␈↓      1␈↓β(1)␈↓         111␈↓β(1)␈↓
␈↓ α∧␈↓␈↓ αd        10       0                                                          *␈↓β(3)␈↓
␈↓ α∧␈↓␈↓ αd    
␈↓ α∧␈↓␈↓ αd                                        Figure 2.
␈↓ α∧␈↓␈↓ αd    

␈↓ α∧␈↓␈↓ αdWhen␈αa␈αsolution␈αdoes␈αnot␈αexist,␈αwe␈αmay␈αor␈αmay␈αnot␈αbe␈αable␈αto␈αdetermine␈αso.
␈↓ α∧␈↓The␈αtable␈α
might␈α"close␈αout"␈α
after␈αa␈α
finite␈αnumber␈αof␈α
steps,␈αthat␈αis,␈α
there␈αmay␈α
be␈αno
␈↓ α∧␈↓more␈α⊂possible␈α⊃entries.␈α⊂ In␈α⊃this␈α⊂case␈α⊂there␈α⊃is␈α⊂no␈α⊃solution.␈α⊂ The␈α⊃column␈α⊂generating
␈↓ α∧␈↓process␈α
might␈α
also␈αcontinue␈α
ad␈α
infinitum;␈αthis␈α
is␈α
detectable␈α
in␈αspecial␈α
cases␈α
but␈αnot␈α
in
␈↓ α∧␈↓general. For example, if any column-pair is ever repeated, there is no solution.

␈↓ α∧␈↓␈↓ αdThe␈α
difficulties␈α
arise␈α
in␈α
step␈α
3)␈α
parts␈α
a3)␈α
and␈α
b3).␈α
 The␈α
entries␈α
afforded␈α
by
␈↓ α∧␈↓these␈αrules,␈αand␈αthus␈α
the␈αtails␈αused␈αelsewhere,␈α
can␈αgrow␈αarbitrarily␈αlong,␈αthus␈α
ruining
␈↓ α∧␈↓our chances for a guarantee of termination of the process.

␈↓ α∧␈↓␈↓ αdOf␈α
course,␈α
we␈α
have␈αnot␈α
shown␈α
that␈α
the␈αproblem␈α
is␈α
unsolvable.␈α
 The␈αmotive
␈↓ α∧␈↓for␈α
introducing␈αa␈α
partial␈α
decision␈αprocedure␈α
is␈αto␈α
offer␈α
students␈αsome␈α
insight␈αinto␈α
the
␈↓ α∧␈↓problem␈α∩itself.␈α∩ The␈α⊃proof␈α∩of␈α∩unsolvability␈α⊃may␈α∩then␈α∩be␈α⊃presented␈α∩as␈α∩usual,␈α⊃by
␈↓ α∧␈↓reduction␈α⊂to␈α⊂the␈α⊂Halting␈α∂Problem␈α⊂or␈α⊂some␈α⊂other␈α∂class␈α⊂of␈α⊂problems␈α⊂known␈α⊂to␈α∂the
␈↓ α∧␈↓students.






␈↓ α∧␈↓␈↓ αdHuffman, D., IS10:Introduction to Cybernetics, Information Sciences Board,

␈↓ α∧␈↓        University␈α
of␈α
California␈α
at␈α
Santa␈αCruz,␈α
Spring␈α
Quarter,␈α
1978.␈α
      ␈αManna,␈α
Z.,
␈↓ α∧␈↓␈↓αMathematical␈α⊃Theory␈α⊂of␈α⊃Computation␈↓,␈α⊂McGraw-Hill,␈α⊃New␈α⊂York,␈α⊃        New␈α⊂York,
␈↓ α∧␈↓1974.␈α-                                                                            ␈α-Minsky,␈α-M.,



␈↓ α∧␈↓␈↓αComputation:␈α∩Finite␈α∪and␈α∩Infinite␈α∪Machines␈↓,␈α∩Prentice-Hall,␈α∪Inc.,␈α∩        Englewood
␈↓ α∧␈↓Cliffs, New Jersey, 1967.



␈↓ α∧␈↓pub is a crock



␈↓ α∧␈↓pub is more of a crock



␈↓ α∧␈↓page it











␈↓ α∧␈↓␈↓ ∧,T A B L E   O F   C O N T E N T S 












␈↓ α∧␈↓␈↓↓{secname}␈↓ 	∨{page!}␈↓{skip; }